package Top101K;
//
///**
// * @Author quan
// * @Description 最长 公共前缀
// * @Date 2023/10/17 21:54
// */
public class a03_BM84_LongestCommonStr {
    public static void main(String[] args) {
        String[] arr ={"abcadae","abc","abca","abc","abcc"};
//        String[] arr ={"abcde","dfg","dfh","dfj"};
        String res = longestCommonPrefix(arr);
        System.out.println(res);
    }
    /**
     * 横向比较的思想：先取出第一个字符串和第二个字符串的公共字串，再将公共字串与第三方字符串比较取出公共字串，依次类推
     */
    public static String longestCommonPrefix (String[] strs) {
        if(strs.length==0 || strs==null){
            return "";
        }
        //1-先初始化公共前缀是第一个字符串
        String common = strs[0];
        for(int i=1;i<strs.length;i++){
            String str = strs[i];
            //2-每个公共前缀与后面字符串的公共部分，以此类推
            common = getCommon(common,str);
            if (common.length() == 0) {
                return "";
            }
        }
        return common;
    }
    /**
     * 求最长公共前缀：注意与最长公共子字符串的区别
     */
    // abd, abced
    public static String getCommon(String str1, String str2){
        //1-找出最短的字符串
        int minStrLen = Math.min(str1.length(),str2.length());
        //2-遍历最短的那个字符串
        int endIndex = 0;
        while (endIndex < minStrLen && str1.charAt(endIndex) == str2.charAt(endIndex)){
            endIndex++;
        }
        return str1.substring(0,endIndex);
    }
}
